﻿
// C# program to find number of bins required using 
// First Fit Decreasing algorithm. 
using System;
using System.Collections.Generic;

public class GFG
{

    /* Copy firstFit() from above */

    // Returns number of bins required using first fit 
    // decreasing offline algorithm 
    static int firstFitDec(List<float> weight, int n, int c)
    {

        // First sort all weights in decreasing order 
        weight.Sort();
        weight.Reverse();

        // Now call first fit for sorted items 
        return firstFit(weight, n, c);
    }

    static int firstFit(List<float> weight, int n, int c)
    {
        // Initialize result (Count of bins) 
        int res = 0;

        // Create an array to store remaining space in bins 
        // there can be at most n bins 
        var bin_rem = new float[n];

        // Place items one by one 
        for (int i = 0; i < n; i++)
        {
            // Find the first bin that can accommodate 
            // weight[i] 
            int j;
            for (j = 0; j < res; j++)
            {
                if (bin_rem[j] >= weight[i])
                {
                    bin_rem[j] = bin_rem[j] - weight[i];
                    break;
                }
            }

            // If no bin could accommodate weight[i] 
            if (j == res)
            {
                bin_rem[res] = c - weight[i];
                res++;
            }
        }
        return res;
    }
}

// This code is contributed by 29AjayKumar 